local Array = require("Array")

local node = {}

function node:pre()
    if self:check(self.prev) then
        return self.prev
    end
    print("节点没有前节点")
end

function node:nex()
    if self:check(self.next) then
        return self.next
    end
    print("节点没有后节点")
end

function node:check(x)
    if x == nil then
        return false
    end
    return true
end

function node:print()
    if self:check(self.value) then
        print("节点的值为："..self.value)
        return
    end
    print("节点的值为： null")
end


--双向链表的节点
local function Node(val, p, n)
    local o = {}
    setmetatable(o,node)
    node.__index = node
    o.prev = p or {}
    o.value = val or {}
    o.next = n or {}
    return o
end

local list = {}

 --输出链表
 function list:print()
    if not self.head.next then
        print("链表为空")
        return
    end
    local temp_node = self.head
    while temp_node.next ~= nil do
        print(temp_node.value)
        temp_node = temp_node.next
    end
    print("===================分割线===================")
end

--添加链表节点并返回当前节点
function list:push(val)
    if type(val) ~= "number" then
        error("请填写有number类型数值")
    end
    if next(self.head) == nil then
        self.head = Node()
        self.head.value = val
        self.tail = self.head
        return self.head
    end
    local temp_node = Node(val)
    temp_node.prev = self.tail
    self.tail.next = temp_node
    self.tail = temp_node
    return temp_node
end

function list:findNode(node)
    if not node then
        error("节点不能为空")
    end
    local temp_node =  self.head
    while temp_node ~= nil and temp_node ~= node do
        temp_node = temp_node.next
    end
    return temp_node
end

--链表插入节点,往右加节点
function list:insert(node, val)
    if not self:findNode(node) then
        error("节点无效")
    end
    if type(val) ~= "number" then
        error("请填写有number类型数值")
    end
    local temp_node = Node(val)
    if not node.next then           --当要插入的就是尾结点时
        temp_node.prev = node.next
        node.next = temp_node
        self.tail = temp_node
        return temp_node
    end
    --因为是右插，不用考虑头结点问题
    -- if not node.prev then           --当要插入的就是头结点时
    --     temp_node.next = node
    --     node.prev = temp_node
    --     self.head = temp_node
    --     return temp_node
    -- end
    temp_node.next = node.next
    temp_node.prev = node
    node.next.prev = temp_node
    node.next = temp_node
    return temp_node
end

--移除对应的节点
function list:remove(node)
    if not self:findNode(node) then
        error("节点无效")
    end
    if not node.prev then
        self.head = node.next
        node.next.prev = nil
        return
    end
    if not node.next then
        self.tail = node.prev
        node.prev.next = nil
        return
    end
    node.prev.next = node.next
    node.next.prev = node.prev
end

--获取链表的头结点
function list:Head()
    if not next(self.head) then
        error("链表没有任何节点")
    end
    return self.head
end

--获取链表的尾结点
function list:Tail()
    if not next(self.head) then
        error("链表没有任何节点")
    end
    return self.tail
end

--退出所有的节点
function list:popAll()
    if not self.head.next then
        print("链表已经为空")
        return
    end
    local temp_node = self.tail
    local popList = Array()
    while temp_node.prev ~= nil do
        popList:push(temp_node.value)
        temp_node = temp_node.prev
    end
    self.head = {}
    self.tail = {}
    return popList
end

--双向链表，未实现左侧添加节点
local function List()
    local o ={}
    setmetatable(o, list)
    list.__index = list
    o.head = {}
    o.tail = {}
    return o
end

return List

